package 删除二叉搜索树中的节点;

/**
 * @author: AirMan
 * @date: 2025/4/8 10:36
 * @description: 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
 * 一般来说，删除节点可分为两个步骤：
 * 首先找到需要删除的节点； 如果找到了，删除它。 说明： 要求算法时间复杂度为 $O(h)$，h 为树的高度。
 */
public class Solution {

    TreeNode parent = null;
    public TreeNode deleteNode(TreeNode root, int key) {
        // 递归
        // 递归的参数：root，key，需要使用全局变量patent记录root的父节点
        // 递归的返回值：void Or TreeNode
        // 递归的终止条件：root == null Or
        // 单层递归逻辑：不需要考虑中间节点，所以前序，中序都可以,自顶向下处理。节点的处理逻辑为判断当前节点是否为key，如果不为key
        // 则根据二叉搜索树的特性进行遍历。
        // 如果root.val == key，进一步判断root的左右孩子是否为空。
        // ① 如果右孩子不为null,那么就将右孩子替换为当前的root。
        // ② 如果右孩子为null，则将左孩子替换为当前的root。
        // ③ 如果右子树不为null，同时左子树不为null。需要将左子树放在右子树的"最左边",然后将右子树替换为当前的root
        // ④ 如果左子树和右子树都为null，按照 ② 进行处理
        // 然后再将root的父节点,指向当前替换的节点，结束遍历

        // 终止逻辑
        if (root == null) {
            return null;
        }

        // 处理当前节点
        if (root.val == key) {
            // 删除root节点
            if (root.right != null) {
                // 右子树不为空，且左子树也不为空时，需要将左子树放在右子树的"最左边"
                if (root.left != null) {
                    TreeNode p = root.right;
                    while (p.left != null) {
                        p = p.left;
                    }
                    p.left = root.left;
                }
                root = root.right;
            } else {
                root = root.left;
            }
            // 父节点指针指向新的节点
            if (parent !=null && parent.val > key) {
                parent.left = root;
            } else if (parent != null){
                parent.right = root;
            }
        } else if (root.val > key) {
            // 从左子树中遍历寻找key
            parent = root;
            deleteNode(root.left, key);
        } else {
            // 从右子树中遍历寻找key
            parent = root;
            deleteNode(root.right, key);
        }
        return root;
    }
}
